The present invention relates to a method and apparatus for controlling a storage means and, more particularly, to a method and apparatus for controlling write processing when a plurality of processing means parallelly generate write requests.
In a recent communication system of an ATM (Asynchronous Transfer Mode) or the like, a plurality of data processing means such as processors perform various processing operations using external or internal storage units.
In such a system, it is important to keep matching of data among the storage units with contents related to each other when the plurality of processors parallelly issue requests for write processing in the storage units. In addition, when the plurality of data processing means are to almost simultaneously use stored data related to each other, use priorities of the data processing means must be taken into consideration, or matching of data along the time axis must be ensured. That is, when a plurality of write requests are generated, the latest data must always be preferentially overwritten.
A general parallel write control method by a plurality of data processing means for a plurality of storage units will be described below by way of some examples.
Assume counter values "0" to "3" described in tables corresponding to identifiers included in headers of communication cells such as ATM cells. For the descriptive convenience, one identifier is assumed to correspond to an index for referring to a table. The entity of this table is stored in a main storage unit outside the communication apparatus.
Every time a cell having an identifier which has not been used for internal processing yet is received by the communication apparatus at a predetermined period (period shorter than the long processing period on the host side), a duplicate of data stored in the main storage unit with an index corresponding to the identifier is stored in a storage unit in the communication apparatus and, more specifically, a cache memory. Upon completion of processing of a cell having the same identifier, the content written in the cache memory is rewritten in the main storage unit.
On the host side outside the communication apparatus, a second data processing means increments the counter values of the tables corresponding to all indices in the main storage unit by one at a predetermined period (long period). In the communication apparatus, every time a cell is received, a first data processing means loads a table corresponding to the identifier from index data in the cache memory and initializes the counter value to "0", thereby reflecting the data in the main storage unit on the cache memory.
The second data processing means independently performs write processing in the main storage unit. The first data processing means independently performs processing for the cache memory. Therefore, unless stored data having the same index are written in overlapping time periods, matching of these stored data is not degraded by write processing in the main storage unit and the cache memory.
However, the main storage unit and the cache memory have the relationship between an entity and a duplicate. When stored data having the same index are independently written in the main storage unit and the cache memory in overlapping time periods, matching of these stored data may be degraded in rewrite processing of the contents stored in the cache memory in the main storage unit.
Assume that the counter value of the table is "1", and the second data processing means increments the counter value to "2". The second data processing means refers to the table in the main storage unit to increment the counter value of the table. At this time point, the counter value of the table is still "1". The second data processing means loads the counter value "1", increments the counter value by one, and writes "2" in the table of the main storage unit.
In some cases, communication cells having identifiers representing the same index are received by the communication apparatus while the second data processing means loads the table and rewrites the counter value. If the first data processing means has initialized the counter value to "0", the counter value "2" rewritten by the second data processing means is based on the counter value "1", i.e., old data before processing by the first data processing means. For this reason, the second data processing means overwrites the counter value "2", although the counter value "1" obtained by incrementing the initialized counter value "0" by one is supposed to be rewritten, thus degrading the matching.
Such mismatching of stored data among the plurality of storage units results from the fact that the data processing means for independently performing processing for the storage units cannot perform real-time processing. Therefore, when the stored data are to be parallelly processed in almost overlapping time periods by a plurality of factors, the problem of mismatching cannot be avoided.
Conventionally, to maintain matching of stored data, two or more data processing means sequentially perform write processing in the corresponding storage units such that the processing periods of the data processing means do not overlap. When a certain data processing means is performing processing including write processing in the storage unit in the same processing block, and another independent data processing means is to perform processing including write processing in the storage unit in the self processing block, less urgent processing must wait until more urgent processing is ended.
More specifically, assume that the second data processing means for incrementing the counter by one and the first data processing means for initializing the counter value to "0" are to perform processing of table data corresponding to the same index in overlapping periods. Even when the data processing means has already started a series of processing operations from counter value load processing to counter value rewrite processing in the counter, processing performed by the second data processing means so far is canceled when the first data processing means having a high urgency level generates a request for loading the same index. After the counter value is initialized to "0" by the first data processing means, the second data processing means loads the counter value again, increments the counter value by one, and rewrites the counter value "1".
Two conventional techniques are used to ensure matching of stored data. One is called an updating scheme. When data is written in a certain storage means on the duplicate side, data in all the remaining storage means on the duplicate side and all storage means on the entity side are updated to the rewritten data.
The other technique is called an invalid scheme. When data is written in a certain storage means on the duplicate side, all the remaining storage means and all storage means on the entity side are notified of the address data of this storage area. With this processing, it is notified that data which has already been written in the storage area at the address is not the latest data, thus invalidate the data in the remaining storage means.
In the updating scheme, when one data processing means has written data in the storage area of a storage means in the same processing block, other data processing means which are going to write data in the same storage area cancel all processing operations. Processing in the storage means in the self processing block must be uselessly performed later again from the beginning.
In the invalid scheme as well, if data stored in the storage subjected to write processing or reference is invalidated, data in the storage area must be read out again to perform processing again from the beginning.
In both the above schema, write processing in the same storage area must be sequentially performed.
Conventionally, to protect matching of stored data, when two or more data processing means are to write data in the same storage area, processing of each data processing means must be sequentially performed.
However, when data stored in the same storage area is to be continuously used for a long time by a data processing means which has a high urgency level and has started processing first, a data processing means which has a low urgency level and therefore must perform processing later waits for its processing. In some cases, the data processing means with the high urgency level cannot complete processing within a predetermined time period when the data processing means with the low urgency level must perform processing.
The above-described counter in the communication table will be considered. While cells having the same index are continuously processed through a pipeline, the first data processing means continuously performs processing using stored data corresponding to the index. In this case, the second data processing means waits for processing. In some cases, the first data processing means cannot complete processing within the time limit that the second data processing means must complete processing.
Conventionally, although data written on the duplicate side is written on the entity side, data newly written on the entity side is not reflected on the duplicate side.
For example, when the first data processing means has written data in the above-described table of the cache memory in which the counter value is stored, the data can be reflected in rewriting the stored data from the cache memory side to the main storage unit side. However, in the prior art, data written by the second data processing means in the main storage unit is not reflected on the cache memory side where the data has already been cached. This causes the following disadvantages.
When cells with the same index data continuously exist at least in the pipeline, stored data which has been loaded once is continuously used without being newly read out from the main storage unit, thereby increasing the cache efficiency. Assume that a cache memory holding stored data corresponding to a certain index is continuously used for a long time. Even when the second data processing means performs processing during this period, rewrite of the stored data corresponding to the index is not reflected on the cache memory side. Therefore, the first data processing means performs processing by continuously using old stored data which has not been rewritten by the second data processing means.
In a communication control apparatus such as an ATM switching system whose development is in progress, processing associated with a cell is performed using an internal cache memory, and processing for the maintenance/operation of all lines is often performed using a main storage unit. In this situation, if the capacity of the storage area of the cache memory is increased to improve the cache efficiency, data for one line may be kept cached for a long time. Assuming that the contents which have been rewritten in the main storage unit are not reflected on the already cached stored data, as in the prior art, if line data is frequently used for cell processing, processing for the maintenance/operation of cache lines degrades matching of stored data in the cache memory which is performing cell processing.
In addition, assume that when write processing by a plurality of data processing means in the same storage area congest, processing is to be sequentially performed. If processing operations at short periods congest during a processing operation at a long period, the processing operation at the long period must wait. However, both the processing operations congest once or more at a long period, the processing operation at the long period is substantially disabled.
Assume that, processing associated with a cell is performed using the internal cache memory, and processing for the maintenance/operation of all lines is performed using the main storage unit. In this case, if a large-scale line is set, the cell arrival frequency of this line becomes high. When a line flow 1/16 that of all lines is set for a line A, a cell arrives at the line A every a 16-cell period. If processing for the maintenance/operation of all lines takes a time corresponding to the 16-cell period, a cell arrives at the line A at a very high probability for this 16-cell period, so the processing for the maintenance/operation of the line A is substantially disabled. This tendency becomes more conspicuous as the line flow increases, and the processing time for a long period increases. If the total line flow is substantially occupied by one line, maintenance/operation processing of lines is completely disabled.